Есть шарики, пронумерованные от $$$1$$$ до $$$n$$$. Также поступают $$$q$$$ запросов:
Посчитайте, какое минимальное количество действий вы можете потратить.
Первая строка содержит числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) - максимальный номер шарика и количество запросов. Далее следуют $$$q$$$ строк в формате:
Выведите единственное число - минимальное количество операций, которое вы можете потратить на запросы.
Подзадача 1. $$$q \le 20$$$ - набирает не менее 15% баллов.
Подзадача 2. В любой момент времени в деке хранится не больше 6 элементов, $$$q \le 1000$$$ - набирает не менее 30% баллов.
Подзадача 3. В любой момент времени в деке хранится не больше 10 элементов, $$$q \le 1000$$$ - набирает не менее 40% баллов.
Подзадача 4. $$$q \cdot n \le 10^6$$$ - набирает не менее 65% баллов.
Подзадача 5. $$$q \le 5000$$$ - набирает не менее 70% баллов.
Подзадачи вложенны друг в друга, т.е. если вы сдали какую-то из подзадач, вы автоматически сдали и все подзадачи до неё.
2 4 add 1 del 1 add 2 del 2
4
8 6 add 5 add 8 del 5 add 1 add 4 del 1
6
В тесте 1 независимо от того, как вы добавите шарики, вы потратите 4 действия (на удаление и на добавление каждого из шариков).
В тесте 2 вам необходимо добавить шарик 5 вниз, шарик 8 вверх, шарик 1 вниз, шарик 4 вверх, тогда вы потратите ровно 6 действий.